# stringTwo是子串，get_next为判断数组
# 此方法用于计算出子串的判定数组
def get_next(stringTwo):
    # prefix中第一个始终为0
    one_next = [0] * len(stringTwo)
    # 比较长度：前缀和后缀相同的长度，同时也用来指向stringTwo表
    length = 0
    i = 1  # 从1位置开始比较
    while i < len(stringTwo):
        if stringTwo[i] == stringTwo[length]:
            length += 1  # 长度加1
            one_next[i] = length  # 新的length就是one_next中i位置的值
            i += 1  # i继续往后走
        else:
            if length > 0:  # 防止length=0时再-1越界
                # length需要回退到pattern表中prefix[length-1]的位置上
                length = one_next[length - 1]
            else:
                one_next[i] = length  # length=0时
                i += 1
    # one_next.insert(0, -1)
    return one_next


def KMP(stringOne, stringTwo):
    one_next = get_next(stringTwo)  # 获取子串的next数组
    i = 0  # i指向主串stringOne
    j = 0  # j指向子串stringTwo
    while i < len(stringOne) and j < len(stringTwo):
        if stringOne[i] == stringTwo[j]:
            i += 1
            j += 1
        else:
            # 当子串第一个字符与主串不同时i往后加1即可
            if j == 0:
                i += 1
            # 否则，j就回退到one_next[j - 1]这个位置，因为这个位置的前缀与此时主串i位置的前缀相同
            else:
                j = one_next[j - 1]  # 如果one_next数组规定是从-1开始的这里就不需要-1
    if j == len(stringTwo):  # 当j已经遍历完子串就返回位置
        return "位置为:%d" % (i - j)
    else:
        return "不存在"


string_one = 'ababababcabaagrvf'
string_two = 'ababcabaa'
print("next数组：", get_next(string_two))
print(KMP(string_one, string_two))
